Ebook in formato Kindle (mobi) - Kindle File Ebook (mobi)

Formato per Iphone, Ipad e Ebook (epub) - Ipad, Iphone and Ebook reader format (epub)

Versione ebook di Readme.it powered by Softwarehouse.it

Il teorema di incompletezza

Questo teoremasi può enunciare come segue:

Se un sistema formale S è consistenteallora l'enunciato C(S) che neesprime la consistenza non è dimostrabile in S.

Dimostrazione

Una volta stabilito il teorema precedentequesto segue quasibanalmente (se - come sempre - non vogliamo essere troppo rigorosi).
Basta osservare che il teorema di indecidibilitàci dice che C(S) implica Vcioè ci dice che se S è consistente allora esisteun enunciato V vero ma non dimostrabile in S. Orase si dimostrasse C(S)sidimostrerebbe anche Vma questo è escluso proprio dal primo teorema...
Semplice in modo sconcertantevero?

Breve discussione

A dispetto della 'semplicità'questo di Gödel è unrisultato della massima importanza: da quando la teoria degli insiemi di Cantorcominciò ad avere successoverso la fine del secolo scorsomolti matematicicominciarono ad usarne le tecnicheanche utilizzando considerazioni implicantiinsiemi infiniti. Al comparireall'inizio del secolodei primi paradossi (o antinomiequella di Russelè del 1902) i matematici cominciarono a pensare che qualcosa fosse sfuggitoloro di manoe si diedero ad una ricerca volta a garantire che i fondamentidella loro scienza fossero (e rimanessero) indenni da simili contraddizioniintrinseche.
Lo stesso Russelinsieme a Whiteheadcominciò a scrivere un'opera monumentalenella quale le regole iniziali dovevano essere scelte con cura proprio perevitare che potessero sorgere paradossi. Quest'opera è Principia Mathematicacitata proprio da Gödel nel titolo del suo lavoro come esempio di sistemaformale intrinsecamente incompleto!
Un altro tentativo fu fatto da uno dei matematici più influenti di questoperiodoDavidHilbertche propose un programma che doveva garantire matematicamentela consistenza del sistema. Secondo questo programma occorreva appunto trovareuna dimostrazione 'matematica' della consistenza della matematica (o di almenodi alcune sue aree). È proprio quanto Gödel dimostra essere impossibile!

Attenzione: questo fatto non ha niente ache vedere con una presunta impossibilità assoluta didimostrare la consistenza di un sistema formale con metodi che lotrascendano! Nel 1936 Gentzenriuscirà a dimostrare che l'aritmetica è consistentema utilizzandometodi che non sono in alcun modo rappresentabili aritmeticamente. Ma sevogliamo essere rompiscatole fino in fondoil problema con similidimostrazioni è che utilizzano ipotesi che non sono in sé più 'certe'della stessa consistenza del sistema che si vuole dimostrareconsistente...

Insommail lavoro di Gödel non lascia spazio a chi vorrebbeconsiderare la matematica solo un 'gioco' formale completoconsistente in modoformalmente dimostrabile.
Ma questo fatto lascia maggior libertà al matematicoche ormai sa non poteresistere alcun sistema formale che possa imprigionare le sue intuizioni. Ilprocedimento di ricerca della verità è un fatto creativonon sempre e soloriducibile ad un puro gioco formale. A me personalmente (e - ne sono certo - atanti altri) questa cosa fa piacere.

E per finire...

Per finireuna chicca: un bell'enunciato indecidibileservito caldo caldo!
Devo anche questo a Penrose chenella prefazione alla riedizione inglese delsuo capolavoro The Emperor's New Mind presenta questo enunciatofacilmente comprensibiledella cui verità (con un po' di pazienza) ci siriesce a convincerema che è indecidibile nell'ambito dell'ordinariaaritmetica!

Prendiamo un numero qualsiasi ed esprimiamolo come somma di potenze di 2eventualmente trasformando in potenze di due anche gli esponenti. Ad esempio:

3 = 2¹ + 1

Ora applichiamo ripetutamente questa semplice procedura:

(a) incrementiamo la 'base' di 1
(b) sottraiamo 1

ottenendo:

3¹ + 1
3¹

ripetiamo (trascurando l'esponente '1'):

4
4-1=3=3x4⁰

dove ho esplicitamente scritto la 'base' raggiuntain questocaso '4'cheper ottenere il corretto risultato '3'deve essere elevataall'esponente '0' (ricordo cheper ogni aa⁰=1). Importanteosservare che da qui in poi la nuova base (cheper l'operazione (a) siincrementa di uno ad ogni passo) non avrà più alcuna influenza sul numeroraggiunto ('3' in questo caso) che d'ora in poi non potrà fare altro chediminuire di uno ad ogni passoin virtù dell'operazione (b). Continuiamo:

3x5⁰
3x5⁰-1=2.

Ci convinciamo senza troppa difficoltà che il nostro numerodi partenza alla fine arriva a zero. Questo è vero per qualunque numero dipartenzain virtù del ragionamento 'informale' scritto sopra in grassetto. Sevuoi fare l'esperimento col numero 4=2² ti puoiconvincere in prima persona che il ragionamento è giusto; armati però dipazienza: si incomincia con 27=3³ e si continua con26424161608483110... ma prima di poter ragionare come ho fattopoco fail numero diventa tanto grande che occorrerebbero la bellezza di121.210.625 cifre per esprimerlo in notazione decimale!

Ma quello che è veramente notevole è che questo enunciatorappresenta un enunciato indecidibileper la normale procedura di induzioneche si utilizza nell'aritmetica ordinaria.

Tengo a osservare esplicitamente chea dispetto della sua indecidibilitàquesto enunciato non solo è veroma abbiamo a disposizione ben tre(!)modi per dimostrarlo! Vediamoli:

In fondo Goodstein il suo teorema l'ha dimostrato!Ha usato una tecnica non riconducibile alla normale procedura di induzionema l'ha dimostrato rigorosamenteanche se al di fuori dell'ordinariaaritmetica.
Kirby e Paris hanno dimostrato che il teorema diGoodstein è una affermazione di Gödel per il 'sistema formale' dellaprocedura di induzione aritmetica. Segue chese noi crediamo alla validitàdi questa proceduracrediamo anche (con le stesso grado di certezzapercosì dire) al teorema di Goodstein.
(Nella terminologia utilizzata nella dimostrazione data quiil nostro programma D 'equivale' alla procedura di induzione aritmetica el'affermazione "il programma P_k(k) nontermina" 'equivale' all'enunciato del teorema di Goodstein. Se credonella validità di Dcredo anche all'affermazione "il programma P_k(k)non termina").
Ci convinciamo che il teorema è vero seguendo ildiscorso (informale) fatto in precedenza. Credo di poter affermare chechiunque (anche chi è dotato di poco intuito matematico) possa venirconvinto da quel ragionamentopurché lo capisca.Naturalmente è lecito richiedere una dimostrazione rigorosae qui sopra neho indicate due.